package Week.D007;

import java.util.Arrays;

public class Solution03 {
    public int connectSticks(int[] sticks) {
        if(sticks==null||sticks.length<=1){
            return 0;
        }
        Arrays.sort(sticks);
        int[] dp=new int[sticks.length];
        int[] length=new int[sticks.length];
        length[0]=sticks[0];
        dp[0]=0;
        for(int i=1;i<sticks.length;i++){
            if(length[i-1]<=sticks[i]){
                length[i]=length[i-1]+sticks[i];

            }else {
                sticks[i-1]=length[i-1];
                sort(i-1,sticks);
                length[i]=sticks[i-1]+sticks[i];
            }
            dp[i]=dp[i-1]+length[i];
        }

        return dp[sticks.length-1];
    }

    private void sort(int index,int[] nums){
        while (index<nums.length-1){
            if(nums[index]>nums[index+1]){
                int temp=nums[index+1];
                nums[index+1]=nums[index];
                nums[index]=temp;
            }else {
                break;
            }
            index++;
        }
    }

}
